'''
深度优先遍历
'''
class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        # 终止条件
        if not root or root == p or root == q: return root
        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)
        # 如果左边返回的是null，则节点确认在右边
        if not left: return right
        # 如果右边返回的是null，则节点确认在左边
        if not right: return left
        # root需要return，递推工作
        return root
